SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>CYK algorithm</title>

</head>

CYK algorithm

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">"CYK" redirects here. For other uses, see <a href="Cyk_(disambiguation)" class="mw-redirect mw-disambig" title="Cyk (disambiguation)">Cyk (disambiguation)</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><caption class="infobox-title">Cocke–Younger–Kasami algorithm (CYK)</caption><tbody><tr><th scope="row" class="infobox-label">Class</th><td class="infobox-data"><a href="Parsing" title="Parsing">Parsing</a> with <a href="Context-free_grammar" title="Context-free grammar">context-free grammars</a></td></tr><tr><th scope="row" class="infobox-label">Data structure</th><td class="infobox-data"><a href="String_(computer_science)" title="String (computer science)">String</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}">

</mrow>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}</annotation>

</semantics>

</math><img src="./1539beef61f0ae858e5ae4665ca4e60bc89efa2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.615ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}" loading="lazy">, where:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is length of the string</li>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |G|}</annotation>

</semantics>

</math><img src="./8258bc41edeb87bfbc8cba8367f29838c0eddc1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.12ex; height:2.843ex;" alt="{\displaystyle |G|}" loading="lazy"> is the size of the CNF grammar</li></ul>

</td></tr></tbody></table>

In <a href="Computer_science" title="Computer science">computer science</a>, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a <a href="Parsing" title="Parsing">parsing</a> <a href="Algorithm" title="Algorithm">algorithm</a> for <a href="Context-free_grammar" title="Context-free grammar">context-free grammars</a> published by Itiroo Sakai in 1961.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a> The algorithm is named after some of its rediscoverers: <a href="John_Cocke_(computer_scientist)" title="John Cocke (computer scientist)">John Cocke</a>, Daniel Younger, <a href="Tadao_Kasami" title="Tadao Kasami">Tadao Kasami</a>, and <a href="Jacob_T._Schwartz" title="Jacob T. Schwartz">Jacob T. Schwartz</a>. It employs <a href="Bottom-up_parsing" title="Bottom-up parsing">bottom-up parsing</a> and <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>.

The standard version of CYK operates only on context-free grammars given in <a href="Chomsky_normal_form" title="Chomsky normal form">Chomsky normal form</a> (CNF). However any context-free grammar may be algorithmically transformed into a CNF grammar expressing the same language (<a href="#CITEREFSipser1997">Sipser 1997</a>).

The importance of the CYK algorithm stems from its high efficiency in certain situations. Using <a href="Big_O_notation" title="Big O notation">big O notation</a>, the <a href="Analysis_of_algorithms" title="Analysis of algorithms">worst case running time</a> of CYK is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}">

</mrow>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}</annotation>

</semantics>

</math><img src="./1539beef61f0ae858e5ae4665ca4e60bc89efa2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.615ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is the length of the parsed string and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left|G\right|}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left|G\right|}</annotation>

</semantics>

</math><img src="./45c9179483098a0a6c22c0ee35baadae5446896d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.12ex; height:2.843ex;" alt="{\displaystyle \left|G\right|}" loading="lazy"> is the size of the CNF grammar <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> (<a href="#CITEREFHopcroftUllman1979">Hopcroft & Ullman 1979</a>, p. 140). This makes it one of the most efficient parsing algorithms in terms of worst-case <a href="Asymptotic_complexity" class="mw-redirect" title="Asymptotic complexity">asymptotic complexity</a>, although other algorithms exist with better average running time in many practical scenarios.

<div class="mw-heading mw-heading2"><h2 id="Standard_form">Standard form</h2></div>

The <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> algorithm requires the context-free grammar to be rendered into <a href="Chomsky_normal_form" title="Chomsky normal form">Chomsky normal form</a> (CNF), because it tests for possibilities to split the current sequence into two smaller sequences. Any context-free grammar that does not generate the empty string can be represented in CNF using only <a href="Formal_grammar#The_syntax_of_grammars" title="Formal grammar">production rules</a> of the forms <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\rightarrow \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\rightarrow \alpha }</annotation>

</semantics>

</math><img src="./13dc432701b1477bc9ba32b0d71c58ecf2d44d9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.845ex; height:2.176ex;" alt="{\displaystyle A\rightarrow \alpha }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\rightarrow BC}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\rightarrow BC}</annotation>

</semantics>

</math><img src="./d006db33dce212be6b03190185ee63f78a27a055.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.888ex; height:2.176ex;" alt="{\displaystyle A\rightarrow BC}" loading="lazy">; to allow for the empty string, one can explicitly allow <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\to \varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\to \varepsilon }</annotation>

</semantics>

</math><img src="./eb30bc1a4b59dcdeb095ecfaad991c8e3b0d26c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.197ex; height:2.176ex;" alt="{\displaystyle S\to \varepsilon }" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> is the start symbol.<a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<div class="mw-heading mw-heading3"><h3 id="As_pseudocode">As pseudocode</h3></div>

The algorithm in <a href="Pseudocode" title="Pseudocode">pseudocode</a> is as follows:

<pre>let the input be a string I consisting of n characters: a1 ... an.

let the grammar contain r nonterminal symbols R1 ... Rr, with start symbol R1.

let P[n,n,r] be an array of booleans. Initialize all elements of P to false.

let back[n,n,r] be an array of lists of backpointing triples. Initialize all elements of back to the empty list.

for each s = 1 to n

for each unit production Rv → as

set P[1,s,v] = true

for each l = 2 to n -- Length of span

for each s = 1 to n-l+1 -- Start of span

for each p = 1 to l-1 -- Partition of span

for each production Ra → Rb Rc

if P[p,s,b] and P[l-p,s+p,c] then

set P[l,s,a] = true,

append <p,b,c> to back[l,s,a]

if P[n,1,1] is true then

I is member of language

return back -- by retracing the steps through back, one can easily construct all possible parse trees of the string.

else

return "not a member of language"

</pre>

<div class="mw-heading mw-heading4"><h4 id="Probabilistic_CYK_(for_finding_the_most_probable_parse)">Probabilistic CYK (for finding the most probable parse)</h4></div>

Allows to recover the most probable parse given the probabilities of all productions.

<pre>let the input be a string I consisting of n characters: a1 ... an.

let the grammar contain r nonterminal symbols R1 ... Rr, with start symbol R1.

let P[n,n,r] be an array of real numbers. Initialize all elements of P to zero.

let back[n,n,r] be an array of backpointing triples.

for each s = 1 to n

for each unit production Rv →as

set P[1,s,v] = Pr(Rv →as)

for each l = 2 to n -- Length of span

for each s = 1 to n-l+1 -- Start of span

for each p = 1 to l-1 -- Partition of span

for each production Ra → Rb Rc

prob_splitting = Pr(Ra →Rb Rc) * P[p,s,b] * P[l-p,s+p,c]

if prob_splitting > P[l,s,a] then

set P[l,s,a] = prob_splitting

set back[l,s,a] = <p,b,c>

if P[n,1,1] > 0 then

find the parse tree by retracing through back

return the parse tree

else

return "not a member of language"

</pre>

</div>

<div class="mw-heading mw-heading3"><h3 id="As_prose">As prose</h3></div>

In informal terms, this algorithm considers every possible substring of the input string and sets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P[l,s,v]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P[l,s,v]}</annotation>

</semantics>

</math><img src="./0b781392de47b61ef1d3b44dd0b0e45e21f0e456.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.018ex; height:2.843ex;" alt="{\displaystyle P[l,s,v]}" loading="lazy"> to be true if the substring of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> starting from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> can be generated from the nonterminal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{v}}</annotation>

</semantics>

</math><img src="./40da33633288f9598f0c6f560681e91bcd8fcee2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.794ex; height:2.509ex;" alt="{\displaystyle R_{v}}" loading="lazy">. Once it has considered substrings of length 1, it goes on to substrings of length 2, and so on. For substrings of length 2 and greater, it considers every possible partition of the substring into two parts, and checks to see if there is some production <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\to B\;C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\to B\;C}</annotation>

</semantics>

</math><img src="./4a68056f70153e48bd457f6b7303c73b43b671fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.533ex; height:2.176ex;" alt="{\displaystyle A\to B\;C}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> matches the first part and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> matches the second part. If so, it records <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> as matching the whole substring. Once this process is completed, the input string is generated by the grammar if the substring containing the entire input string is matched by the start symbol.

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

This is an example grammar:

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}{\ce {S}}&\ {\ce {->NP\ VP}}\\{\ce {VP}}&\ {\ce {->VP\ PP}}\\{\ce {VP}}&\ {\ce {->V\ NP}}\\{\ce {VP}}&\ {\ce {->eats}}\\{\ce {PP}}&\ {\ce {->P\ NP}}\\{\ce {NP}}&\ {\ce {->Det\ N}}\\{\ce {NP}}&\ {\ce {->she}}\\{\ce {V}}&\ {\ce {->eats}}\\{\ce {P}}&\ {\ce {->with}}\\{\ce {N}}&\ {\ce {->fish}}\\{\ce {N}}&\ {\ce {->fork}}\\{\ce {Det}}&\ {\ce {->a}}\end{aligned}}}">

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\ce {S}}&\ {\ce {->NP\ VP}}\\{\ce {VP}}&\ {\ce {->VP\ PP}}\\{\ce {VP}}&\ {\ce {->V\ NP}}\\{\ce {VP}}&\ {\ce {->eats}}\\{\ce {PP}}&\ {\ce {->P\ NP}}\\{\ce {NP}}&\ {\ce {->Det\ N}}\\{\ce {NP}}&\ {\ce {->she}}\\{\ce {V}}&\ {\ce {->eats}}\\{\ce {P}}&\ {\ce {->with}}\\{\ce {N}}&\ {\ce {->fish}}\\{\ce {N}}&\ {\ce {->fork}}\\{\ce {Det}}&\ {\ce {->a}}\end{aligned}}}</annotation>

</semantics>

</math><img src="./cab1e35d37e81b32275f1afb440fcba4fdc4378e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -17.505ex; width:16.728ex; height:36.176ex;" alt="{\displaystyle {\begin{aligned}{\ce {S}}&\ {\ce {->NP\ VP}}\\{\ce {VP}}&\ {\ce {->VP\ PP}}\\{\ce {VP}}&\ {\ce {->V\ NP}}\\{\ce {VP}}&\ {\ce {->eats}}\\{\ce {PP}}&\ {\ce {->P\ NP}}\\{\ce {NP}}&\ {\ce {->Det\ N}}\\{\ce {NP}}&\ {\ce {->she}}\\{\ce {V}}&\ {\ce {->eats}}\\{\ce {P}}&\ {\ce {->with}}\\{\ce {N}}&\ {\ce {->fish}}\\{\ce {N}}&\ {\ce {->fork}}\\{\ce {Det}}&\ {\ce {->a}}\end{aligned}}}" loading="lazy"></dd></dl>

Now the sentence she eats a fish with a fork is analyzed using the CYK algorithm. In the following table, in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P[i,j,k]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P[i,j,k]}</annotation>

</semantics>

</math><img src="./ec16c23ab686cf2fa698264b3afa003cde84b876.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.079ex; height:2.843ex;" alt="{\displaystyle P[i,j,k]}" loading="lazy">, i is the number of the row (starting at the bottom at 1), and j is the number of the column (starting at the left at 1).

<caption>CYK table

</caption>

<td>S

</td></tr>

<tr>

<td>VP

</td></tr>

<tr>

<td>

</td></tr>

<tr>

<td>

</td></tr>

<tr>

<td>PP

</td></tr>

<tr>

<td>NP

</td></tr>

<tr>

<td>N

</td></tr>

<td>fork

</td></tr></tbody></table>

For readability, the CYK table for P is represented here as a 2-dimensional matrix M containing a set of non-terminal symbols, such that Rk is in ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M[i,j]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M[i,j]}</annotation>

</semantics>

</math><img src="./46a618d7ccbbfcf5ac18e353c34883aa739e49da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.53ex; height:2.843ex;" alt="{\displaystyle M[i,j]}" loading="lazy">⁠ if, and only if, ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P[i,j,k]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P[i,j,k]}</annotation>

</semantics>

</math><img src="./ec16c23ab686cf2fa698264b3afa003cde84b876.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.079ex; height:2.843ex;" alt="{\displaystyle P[i,j,k]}" loading="lazy">⁠.

In the above example, since a start symbol S is in ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M[7,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M[7,1]}</annotation>

</semantics>

</math><img src="./3febc58b09f93ccd1f6ce41f7bd10a503e435828.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.095ex; height:2.843ex;" alt="{\displaystyle M[7,1]}" loading="lazy">⁠, the sentence can be generated by the grammar.

<div class="mw-heading mw-heading2"><h2 id="Extensions">Extensions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Generating_a_parse_tree">Generating a parse tree</h3></div>

The above algorithm is a <a href="Recognizer" class="mw-redirect" title="Recognizer">recognizer</a> that will only determine if a sentence is in the language. It is simple to extend it into a <a href="Parser" class="mw-redirect" title="Parser">parser</a> that also constructs a <a href="Parse_tree" title="Parse tree">parse tree</a>, by storing parse tree nodes as elements of the array, instead of the boolean 1. The node is linked to the array elements that were used to produce it, so as to build the tree structure. Only one such node in each array element is needed if only one parse tree is to be produced. However, if all parse trees of an ambiguous sentence are to be kept, it is necessary to store in the array element a list of all the ways the corresponding node can be obtained in the parsing process. This is sometimes done with a second table B[n,n,r] of so-called backpointers.

The end result is then a shared-forest of possible parse trees, where common trees parts are factored between the various parses. This shared forest can conveniently be read as an <a href="Ambiguous_grammar" title="Ambiguous grammar">ambiguous grammar</a> generating only the sentence parsed, but with the same ambiguity as the original grammar, and the same parse trees up to a very simple renaming of non-terminals, as shown by <a href="#CITEREFLang1994">Lang (1994)</a>.

<div class="mw-heading mw-heading3"><h3 id="Parsing_non-CNF_context-free_grammars">Parsing non-CNF context-free grammars</h3></div>

As pointed out by <a href="#CITEREFLangeLeiß2009">Lange & Leiß (2009)</a>, the drawback of all known transformations into Chomsky normal form is that they can lead to an undesirable bloat in grammar size. The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side. Using <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> to denote the size of the original grammar, the size blow-up in the worst case may range from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g^{2}}</annotation>

</semantics>

</math><img src="./5f9d6efa0fe9ea0a23f2f92c6b309cea94f4441b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.172ex; height:3.009ex;" alt="{\displaystyle g^{2}}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{2g}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{2g}}</annotation>

</semantics>

</math><img src="./f74286c753a0df5339407a63ef62e39880a6e1d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.006ex; height:2.676ex;" alt="{\displaystyle 2^{2g}}" loading="lazy">, depending on the transformation algorithm used. For the use in teaching, Lange and Leiß propose a slight generalization of the CYK algorithm, "without compromising efficiency of the algorithm, clarity of its presentation, or simplicity of proofs" (<a href="#CITEREFLangeLeiß2009">Lange & Leiß 2009</a>).

<div class="mw-heading mw-heading3"><h3 id="Parsing_weighted_context-free_grammars">Parsing weighted context-free grammars</h3></div>

It is also possible to extend the CYK algorithm to parse strings using <a href="Weighted_context-free_grammar" class="mw-redirect" title="Weighted context-free grammar">weighted</a> and <a href="Stochastic_context-free_grammar" class="mw-redirect" title="Stochastic context-free grammar">stochastic context-free grammars</a>. Weights (probabilities) are then stored in the table P instead of booleans, so P[i,j,A] will contain the minimum weight (maximum probability) that the substring from i to j can be derived from A. Further extensions of the algorithm allow all parses of a string to be enumerated from lowest to highest weight (highest to lowest probability).

<div class="mw-heading mw-heading4"><h4 id="Numerical_stability">Numerical stability</h4></div>

When the probabilistic CYK algorithm is applied to a long string, the splitting probability can become very small due to multiplying many probabilities together. This can be dealt with by summing log-probability instead of multiplying probabilities.

<div class="mw-heading mw-heading3"><h3 id="Valiant's_algorithm">Valiant's algorithm</h3></div>

The <a href="Analysis_of_algorithms" title="Analysis of algorithms">worst case running time</a> of CYK is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n^{3}\cdot |G|)}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{3}\cdot |G|)}</annotation>

</semantics>

</math><img src="./429ad4ecb51ecc65233048a22750741032a0a4a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.866ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{3}\cdot |G|)}" loading="lazy">, where n is the length of the parsed string and |G| is the size of the CNF grammar G. This makes it one of the most efficient algorithms for recognizing general context-free languages in practice. <a href="#CITEREFValiant1975">Valiant (1975)</a> gave an extension of the CYK algorithm. His algorithm computes the same parsing table

as the CYK algorithm; yet he showed that <a href="Matrix_multiplication_algorithm#Sub-cubic_algorithms" title="Matrix multiplication algorithm">algorithms for efficient multiplication</a> of <a href="Boolean_matrix" title="Boolean matrix">matrices with 0-1-entries</a> can be utilized for performing this computation.

Using the <a href="Coppersmith%E2%80%93Winograd_algorithm" class="mw-redirect" title="Coppersmith–Winograd algorithm">Coppersmith–Winograd algorithm</a> for multiplying these matrices, this gives an asymptotic worst-case running time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2.38}\cdot |G|)}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2.38}\cdot |G|)}</annotation>

</semantics>

</math><img src="./a3fa20017441214a8e9ac2b238f7d2a4fec8b9ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.932ex; height:3.176ex;" alt="{\displaystyle O(n^{2.38}\cdot |G|)}" loading="lazy">. However, the constant term hidden by the <a href="Big_O_Notation" class="mw-redirect" title="Big O Notation">Big O Notation</a> is so large that the Coppersmith–Winograd algorithm is only worthwhile for matrices that are too large to handle on present-day computers (<a href="#CITEREFKnuth1997">Knuth 1997</a>), and this approach requires subtraction and so is only suitable for recognition. The dependence on efficient matrix multiplication cannot be avoided altogether: <a href="#CITEREFLee2002">Lee (2002)</a> has proved that any parser for context-free grammars working in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3-\varepsilon }\cdot |G|)}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3-\varepsilon }\cdot |G|)}</annotation>

</semantics>

</math><img src="./5159abca9ceecc9defb8669808cc6c26df3d4b4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.876ex; height:3.176ex;" alt="{\displaystyle O(n^{3-\varepsilon }\cdot |G|)}" loading="lazy"> can be effectively converted into an algorithm computing the product of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n\times n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n\times n)}</annotation>

</semantics>

</math><img src="./b0e369b52ee16c33d83f7cd0eb0f562fd91b7f3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.439ex; height:2.843ex;" alt="{\displaystyle (n\times n)}" loading="lazy">-matrices with 0-1-entries in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3-\varepsilon /3})}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3-\varepsilon /3})}</annotation>

</semantics>

</math><img src="./4715dc21b792da639805a6bbd65289f71723376a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.72ex; height:3.343ex;" alt="{\displaystyle O(n^{3-\varepsilon /3})}" loading="lazy">, and this was extended by Abboud et al.<a href="#cite_note-4">[4]</a> to apply to a constant-size grammar.

<ul><li><a href="GLR_parser" title="GLR parser">GLR parser</a></li>

<li><a href="Earley_parser" title="Earley parser">Earley parser</a></li>

<li><a href="Packrat_parser" title="Packrat parser">Packrat parser</a></li>

<li><a href="Inside%E2%80%93outside_algorithm" title="Inside–outside algorithm">Inside–outside algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGrune2008" class="citation book cs1">Grune, Dick (2008). Parsing techniques : a practical guide (2nd ed.). New York: Springer. p. 579. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-20248-8</bdi>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> Itiroo Sakai, “Syntax in universal translation”. In Proceedings 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Her Majesty’s Stationery Office, London, p. 593-608, 1962.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFSipser2006" class="citation book cs1">Sipser, Michael (2006). Introduction to the theory of computation (2nd ed.). Boston: Thomson Course Technology. Definition 2.8. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-534-95097-3</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/58544333">58544333</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFAbboudBackursWilliams2015" class="citation arxiv cs1">Abboud, Amir; Backurs, Arturs; Williams, Virginia Vassilevska (2015-11-05). "If the Current Clique Algorithms are Optimal, so is Valiant's Parser". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1504.01431">1504.01431</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CC">cs.CC</a>].</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Sources">Sources</h2></div>

<ul><li><cite id="CITEREFSakai1962" class="citation conference cs1">Sakai, Itiroo (1962). Syntax in universal translation. 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Teddington, England. Vol. II. London: Her Majesty’s Stationery Office. pp. 593–608.</cite></li>

<li><cite id="CITEREFCockeSchwartz1970" class="citation techreport cs1"><a href="John_Cocke_(computer_scientist)" title="John Cocke (computer scientist)">Cocke, John</a>; Schwartz, Jacob T. (April 1970). <a rel="nofollow" class="external text" href="http://www.softwarepreservation.org/projects/FORTRAN/CockeSchwartz_ProgLangCompilers.pdf">Programming languages and their compilers: Preliminary notes</a> (PDF) (Technical report) (2nd revised ed.). <a href="Courant_Institute_of_Mathematical_Sciences" title="Courant Institute of Mathematical Sciences">CIMS</a>, <a href="New_York_University" title="New York University">NYU</a>.</cite></li>

<li><cite id="CITEREFHopcroftUllman1979" class="citation book cs1"><a href="John_E._Hopcroft" class="mw-redirect" title="John E. Hopcroft">Hopcroft, John E.</a>; <a href="Jeffrey_D._Ullman" class="mw-redirect" title="Jeffrey D. Ullman">Ullman, Jeffrey D.</a> (1979). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoau00hopc">Introduction to Automata Theory, Languages, and Computation</a>. Reading/MA: Addison-Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-02988-X</bdi>.</cite></li>

<li><cite id="CITEREFKasami1965" class="citation techreport cs1"><a href="Tadao_Kasami" title="Tadao Kasami">Kasami, T.</a> (1965). An efficient recognition and syntax-analysis algorithm for context-free languages (Technical report). <a href="Air_Force_Cambridge_Research_Laboratories" class="mw-redirect" title="Air Force Cambridge Research Laboratories">AFCRL</a>. 65-758.</cite></li>

<li><cite id="CITEREFKnuth1997" class="citation book cs1"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald E.</a> (November 14, 1997). The Art of Computer Programming Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley Professional. p. 501. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89684-2</bdi>.</cite></li>

<li><cite id="CITEREFLang1994" class="citation journal cs1">Lang, Bernard (1994). "Recognition can be harder than parsing". <a href="Computational_Intelligence_(journal)" title="Computational Intelligence (journal)">Comput. Intell.</a> 10 (4): 486–494. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.6982">10.1.1.50.6982</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2Fj.1467-8640.1994.tb00011.x">10.1111/j.1467-8640.1994.tb00011.x</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5873640">5873640</a>.</cite></li>

<li><cite id="CITEREFLangeLeiß2009" class="citation journal cs1">Lange, Martin; Leiß, Hans (2009). <a rel="nofollow" class="external text" href="http://www.informatica-didactica.de/index.php?page=LangeLeiss2009">"To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm"</a>. Informatica Didactica. 8.</cite></li>

<li><cite id="CITEREFLee2002" class="citation journal cs1"><a href="Lillian_Lee_(computer_scientist)" title="Lillian Lee (computer scientist)">Lee, Lillian</a> (2002). "Fast context-free grammar parsing requires fast Boolean matrix multiplication". <a href="Journal_of_the_ACM" title="Journal of the ACM">J. ACM</a>. 49 (1): 1–15. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0112018">cs/0112018</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F505241.505242">10.1145/505241.505242</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1243491">1243491</a>.</cite></li>

<li><cite id="CITEREFSipser1997" class="citation book cs1"><a href="Michael_Sipser" title="Michael Sipser">Sipser, Michael</a> (1997). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoth00sips/page/99">Introduction to the Theory of Computation</a> (1st ed.). IPS. p. <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoth00sips/page/99">99</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-534-94728-X</bdi>.</cite></li>

<li><cite id="CITEREFValiant1975" class="citation journal cs1"><a href="Leslie_Valiant" title="Leslie Valiant">Valiant, Leslie G.</a> (1975). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0022-0000%2875%2980046-8">"General context-free recognition in less than cubic time"</a>. <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">J. Comput. Syst. Sci.</a> 10 (2): 308–314. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0022-0000%2875%2980046-8">10.1016/s0022-0000(75)80046-8</a>.</cite></li>

<li><cite id="CITEREFYounger1967" class="citation journal cs1">Younger, Daniel H. (February 1967). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0019-9958%2867%2980007-x">"Recognition and parsing of context-free languages in time n3"</a>. <a href="Information_and_Computation" title="Information and Computation">Inform. Control</a>. 10 (2): 189–208. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0019-9958%2867%2980007-x">10.1016/s0019-9958(67)80007-x</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://raw.org/tool/cyk-algorithm/">Interactive Visualization of the CYK algorithm</a></li>

<li><a rel="nofollow" class="external text" href="https://martinlaz.github.io/demos/cky.html">CYK parsing demo in JavaScript</a></li>

<li><a rel="nofollow" class="external text" href="https://www.swisseduc.ch/informatik/exorciser/">Exorciser is a Java application to generate exercises in the CYK algorithm as well as Finite State Machines, Markov algorithms etc</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Parsing_algorithms116" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Parsing_algorithms116" style="font-size:114%;margin:0 4em"><a href="Parsing" title="Parsing">Parsing algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Top-down_parsing" title="Top-down parsing">Top-down</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Earley_parser" title="Earley parser">Earley</a></li>

<li><a href="Recursive_descent_parser" title="Recursive descent parser">Recursive descent</a>

<ul><li><a href="Tail_recursive_parser" title="Tail recursive parser">Tail recursive</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Bottom-up_parsing" title="Bottom-up parsing">Bottom-up</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Precedence

<ul><li><a href="Simple_precedence_parser" title="Simple precedence parser">Simple</a></li>

<li><a href="Operator-precedence_parser" title="Operator-precedence parser">Operator</a>

<ul><li><a href="Shunting_yard_algorithm" title="Shunting yard algorithm">Shunting-yard</a></li></ul></li></ul></li>

<ul><li><a href="Simple_LR_parser" title="Simple LR parser">Simple</a></li>

<li><a href="LALR_parser" title="LALR parser">Look-ahead</a></li>

<li><a href="Canonical_LR_parser" title="Canonical LR parser">Canonical</a></li>

<li><a href="GLR_parser" title="GLR parser">Generalized</a></li></ul></li>

<li><a href="Recursive_ascent_parser" title="Recursive ascent parser">Recursive ascent</a></li>

<li><a href="Shift-reduce_parser" title="Shift-reduce parser">Shift-reduce</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mixed, other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parser_combinator" title="Parser combinator">Combinator</a></li>

<li><a href="Chart_parser" title="Chart parser">Chart</a>

<ul><li><a href="Left_corner_parser" title="Left corner parser">Left corner</a></li></ul></li>

<li>Statistical</li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related topics</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Definite_clause_grammar" title="Definite clause grammar">Definite clause grammar</a></li>

<li><a href="Deterministic_parsing" title="Deterministic parsing">Deterministic parsing</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Memoization" title="Memoization">Memoization</a></li>

<li><a href="Compiler-compiler" title="Compiler-compiler">Parser generator</a>

<li><a href="Parse_tree" title="Parse tree">Parse tree</a></li>

<li><a href="Scannerless_parsing" title="Scannerless parsing">Scannerless parsing</a></li>

<li><a href="History_of_compiler_construction" title="History of compiler construction">History of compiler construction</a></li>

<li><a href="Comparison_of_parser_generators" title="Comparison of parser generators">Comparison of parser generators</a></li>

<li><a href="Operator-precedence_grammar" title="Operator-precedence grammar">Operator-precedence grammar</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-17" href="https://en.wikipedia.org/wiki/?title=CYK_algorithm&oldid=1300921646">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>